| 翻訳と辞書 |
| Mac Lane's planarity criterion ： ウィキペディア英語版 |
Mac Lane's planarity criterion
In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if
the cycle space of the graph (taken modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors.
==Statement==
For any cycle in a graph , one can form an -dimensional 0-1 vector that has a 1 in the coordinate positions corresponding to edges in and a 0 in the remaining coordinate positions. The cycle space of the graph is the vector space formed by all possible linear combinations of vectors formed in this way. In Mac Lane's characterization, is a vector space over the finite field with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A ''2-basis'' of is a basis of with the property that, for each edge in , at most two basis vectors have nonzero coordinates in the position corresponding to . Then, stated more formally, Mac Lane's characterization is that the planar graphs are exactly the graphs that have a 2-basis.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Mac Lane's planarity criterion」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|